// mutex.cc - system mutexes

/** 
 * This user side implementation needs a bit of work. This is just a simple
 * adaptation from the kernel side objects and should probably be handled
 * differently than it is. It also depends on having access to eflags.IF, which
 * is going away (it's really bad to expose to generic userland).
 */

/*
   Copyright 2006 Corey Tabaka

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/

#include <mutex.h>
#include <syscall.h>
#include <atomic.h>

// defined in mutex_asm.asm
extern "C"
int mutex_exchange(int set, volatile int *test);
extern "C"
int mutex_atomicSet(int src, volatile int *dest);

/*
 * Linked list utilities.
 *
 * IMPORTANT: Always have the respective spinlock locked befor calling these.
 */
static inline void queue_append(mutex_tid_node *node, mutex_t *mutex) {
	node->next = NULL;
	
	if (mutex->head) {
		node->prev = mutex->tail;
		mutex->tail->next = node;
	} else {
		node->prev = NULL;
		mutex->head = node;
	}
	
	mutex->tail = node;
}

static inline void queue_remove(mutex_tid_node *node, mutex_t *mutex) {
	bool isHead = node == mutex->head;
	bool isTail = node == mutex->tail;
	
	if (isTail) {
		mutex->tail = node->prev;
		
		if (!isHead) {
			node->prev->next = NULL;
		}
	}
	
	if (isHead) {
		mutex->head = node->next;
		
		if (!isTail) {
			node->next->prev = NULL;
		}
	}
	
	if (!isHead && !isTail) {
		node->prev->next = node->next;
		node->next->prev = node->prev;
	}
}

/*
 * Initialize a dynamically allocated mutex_t
 */
void mutex_init(mutex_t *mutex) {
	interrupt_mutex_init(&mutex->lock);
	
	mutex->count = 0;
	mutex->head = NULL;
	mutex->tail = NULL;
}

#if 1
/*
 * Attempt to lock the mutex, entering wait state on failure.
 */
void mutex_wait(mutex_t *mutex) {
	// wait while the mutex is locked
	while (mutex_exchange(1, &mutex->count) != 0) {
		/*
		 * Allocate a node to hold the tid for this task.
		 * mutex_signal is responsible for freeing the node
		 * at the head of the queue.
		 */
		mutex_tid_node *node = new mutex_tid_node;
		node->tid = syscall(SYSCALL_THREAD, SYSCALL_THREAD_GET_TID);
		
		/*
		 * Lock the mutex queue access lock. Interrupt mutexes are used
		 * to maintain a consistent bounded wait queue. If spinlocks were
		 * used instead, task switches could occur during queue operations,
		 * wasting context switches and burning cycles spinning.
		 */
		spinlock_wait(&mutex->lock.spinlock);
		
		// add this task to the list of waiting tasks
		queue_append(node, mutex);
		
		spinlock_signal(&mutex->lock.spinlock);
		
		// block until notify(tid)
		WAIT();
	}
}

/*
 * Attempt to lock the mutex, returning status. This function does not block
 * on an already locked mutex.
 *
 * Returns 0 (previously unlocked) on success, nonzero on failure.
 */
int mutex_try(mutex_t *mutex) {
	return mutex_exchange(1, &mutex->count);
}

/*
 * Release a locked mutex. Wake the head of the wait queue and free resources.
 */
void mutex_signal(mutex_t *mutex) {
	spinlock_wait(&mutex->lock.spinlock);
	
	tid_t tid = 0;
	bool wake = false;
	
	// see if another task is waiting on this mutex
	if (mutex->head) {
		mutex_tid_node *node = mutex->head;
		tid = node->tid;
		wake = true;
		
		// remove the task from the queue
		queue_remove(node, mutex);
		
		delete node;
	}
	
	spinlock_signal(&mutex->lock.spinlock);
	
	// unlock mutex
	//mutex->count = 0;
	mutex_exchange(0, &mutex->count);
	
	if (wake) {
		NOTIFY(tid);
		
		// give other tasks a chance to obtain the lock on very fast systems
		YIELD();
	}
}		
#endif

void semaphore_init(semaphore_t *sem, int count) {
	spinlock_init(&sem->lock.spinlock);
	sem->count = count;
	sem->head = NULL;
	sem->tail = NULL;
}

void semaphore_wait(semaphore_t *sem) {
	if (atomic_add(-1, &sem->count) <= 0) {
		mutex_tid_node *node = new mutex_tid_node;
		node->tid = syscall(SYSCALL_THREAD, SYSCALL_THREAD_GET_TID);
		
		spinlock_wait(&sem->lock.spinlock);
		
		// add this task to the list of waiting tasks
		queue_append(node, sem);
		
		spinlock_signal(&sem->lock.spinlock);
		
		WAIT();
	}
}

void semaphore_signal(semaphore_t *sem) {
	spinlock_wait(&sem->lock.spinlock);
	tid_t tid = 0;
	bool wake = false;
	
	if (atomic_add(1, &sem->count) <= 0) {
		// see if another task is waiting on this mutex
		if (sem->head) {
			mutex_tid_node *node = sem->head;
			tid = node->tid;
			wake = true;
			
			// remove the task from the queue
			queue_remove(node, sem);
			
			delete node;
		}
	}
	
	spinlock_signal(&sem->lock.spinlock);
	
	if (wake) {
		NOTIFY(tid);
		
		// give other tasks a chance to obtain the lock on very fast systems
		YIELD();
	}
}
